# source: https://leetcode.com/problems/my-calendar-iii/ 一刷 2024.11.27
from sortedcontainers import SortedDict
class MyCalendarThree:

    def __init__(self):
        self.d = SortedDict()

    def book(self, startTime: int, endTime: int) -> int:
        self.d[startTime] = self.d.get(startTime, 0) + 1
        self.d[endTime] = self.d.get(endTime, 0) - 1
        mx, cnt = 0, 0
        for v in self.d.keys():
            cnt += self.d[v]
            mx = max(mx, cnt)
        return mx


# Your MyCalendarThree object will be instantiated and called as such:
# obj = MyCalendarThree()
# param_1 = obj.book(startTime,endTime)

# source: https://leetcode.cn/problems/sliding-subarray-beauty/ 滑动窗口
from sortedcontainers import SortedList
class Solution:
    def getSubarrayBeauty(self, nums: List[int], k: int, x: int) -> List[int]:
        array = SortedList()
        i = 0
        ans = []
        for j, v in enumerate(nums):
            array.add(v)
            if j-i+1 > k:
                array.remove(nums[i])
                i += 1
            if j-i+1 == k:
                ans.append(array[x-1] if array[x-1] < 0 else 0)
        return ans

# source: https://leetcode.cn/problems/defuse-the-bomb/submissions/ 定长滑动窗口 二刷 一刷 2024.5.5
class Solution:
    def decrypt(self, code: List[int], k: int) -> List[int]:
        if k == 0:
            return [0]*len(code)
        ans = []
        i, total = 0, 0
        j = 1
        if k < 0:
            code = code[::-1]
        while i < len(code):
            total += code[j % len(code)]
            if j-i > abs(k):
                total -= code[(i+1) % len(code)]
                i += 1
            if i < len(code) and j-i == abs(k):
                ans.append(total)
            j += 1
        return ans if k > 0 else ans[::-1]

# source: https://leetcode.cn/problems/minimum-number-of-flips-to-make-the-binary-string-alternating/ 滑动窗口 难
class Solution:
    def minFlips(self, s: str) -> int:
        n = len(s)
        s01 = '01'
        cnt = 0
        for i, v in enumerate(s):
            if s01[i%2] == v:
                cnt += 1
        ans = min(cnt, n-cnt)

        for i in range(n, 2*n, 1):
            if s[(i-n)%n] == s01[(i-n)%2]:
                cnt -= 1
            if s[i%n] == s01[i%2]:
                cnt += 1
            ans = min(ans, min(cnt, n-cnt))
        return ans